package Algorithm.DynamicPlanning;

public class Code20_maxIncreChain {

    public static int maxIncreChain(int[][] ma){
        if (ma == null || ma.length == 0 || ma[0].length == 0){
            return -1;
        }
        int[][] dp = new int[ma.length][ma[0].length];
        int res = 0;
        for (int i = 0; i < ma.length; i++) {
            for (int j = 0; j < ma[0].length; j++) {
                res = Math.max(res, dfs(ma, i, j, dp));
            }
        }
        return res;
    }

    public static int dfs(int[][] ma, int i, int j, int[][] dp){
        int p1 = 0;
        int p2 = 0;
        int p3 = 0;
        int p4 = 0;
        if (dp[i][j] != 0){
            return dp[i][j];
        }
        if (i - 1 >= 0 && ma[i - 1][j] > ma[i][j]){
            p1 = dfs(ma, i - 1, j, dp);
        }
        if (j - 1 >= 0 && ma[i][j - 1] > ma[i][j]){
            p2 = dfs(ma, i, j - 1, dp);
        }
        if (i + 1 < ma.length && ma[i + 1][j] > ma[i][j]){
            p3 = dfs(ma, i + 1, j, dp);
        }
        if (j + 1 < ma[0].length && ma[i][j + 1] > ma[i][j]){
            p4 = dfs(ma, i, j + 1, dp);
        }
        int res = 1 + Math.max(p1, Math.max(p2, Math.max(p3, p4)));
        dp[i][j] = res;
        return res;
    }

    public static void main(String[] args) {

    }
}
